/*
 * @lc app=leetcode.cn id=44 lang=cpp
 *
 * [44] 通配符匹配
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool isMatch(string s, string p)
    {
        const int s_len = s.length();
        const int p_len = p.length();
        if (p_len == 0)
            return s_len == 0;

        vector<vector<bool>> dp(s_len + 1, vector<bool>(p_len + 1, 0));

        for(int i= 1; i <= p_len && p[i-1] == '*'; i++)
            dp[0][i] = true;

        dp[0][0] = true;


        for(int i = 1; i <= s_len; i++)
        {
            for(int j = 1; j <= p_len; j++)
            {
                if(p[j-1] == '*')
                {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }
                else if(p[j-1] == '?' || s[i-1] == p[j-1])
                {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }

        return dp[s_len][p_len];
    }
};

// int main()
// {
//     cout << Solution().isMatch("adceb", "*a*b") << endl;
//     return 0;
// }
// @lc code=end
